/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86131
 * Date: 2024-01-23
 * Time: 9:14
 */

//插入排序
public class Sort {
    public static void inserSort(int[] array) {
        for (int i = 1; i < array.length; i++) {  //i从1下标开始遍历整个数组
            int tmp = array[i]; //创建一个变量存储数值
            int j = i - 1;  //j的下标位置
            for (; j >= 0; j--) {
                if (array[j] > tmp) { //如果下标j大于变量的值,则需要调整
                    array[j + 1] = array[j];  //放到j+1所在的位置
                } else {
                    //array[j+1] = tmp; //变量放回原位;
                    break; //跳出
                }
            }
            array[j + 1] = tmp; //最后一次比较，因为j--到-1的位置，所以 放回0下标的位置
        }
    }


    //希尔排序 不稳定
    public static void shellSort(int[] array) {
        int gap = array.length; //根据元素个数分组数 例如 10
        while (gap > 1) {
            gap /= 2; //5,2,1
            shell(array, gap);
        }
    }

    private static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j = j - gap) {  //因为间隔gap个数，所以j要减gap
                if (array[j] > tmp) {  //j下标元素大于tmp变量时，就插入排序交换
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }


    //直接选择排序
    //时间复杂度：O(N^2)
    //空间复杂度：O(1)
    //稳定性：不稳定
    public static void selectSort(int[] arrary) {
        for (int i = 0; i < arrary.length; i++) {
            int minIndex = i;  //先把i确定为最小值的下标，后续如果碰到比它小的数值就更新minIndex
            int j = i + 1;  //确定j下标的位置
            for (; j < arrary.length; j++) {
                if (arrary[minIndex] > arrary[j]) {
                    //min一定存储最小值的下标
                    minIndex = j;  //J下标的值更小就更新minIndex的值
                }
            }
            //走到这一步就说明这一趟minIndex存储最小值的下标，然后就可以和i下标的值进行交换
            swap(arrary, i, minIndex);
        }
    }

    private static void swap(int[] array, int i, int j) {
        //交换
        int tmp = array[j];
        array[j] = array[i];
        array[i] = tmp;
    }

    public static void selectSort2(int[] arrary) {
        int left = 0;
        int right = arrary.length - 1;
        while (left < right) {
            int minIndex = left;
            int maxIndex = right;
            for (int i = left + 1; i < right; i++) {
                if (arrary[i] < arrary[minIndex]) {
                    minIndex = i;
                }
                if (arrary[i] > arrary[maxIndex]) {
                    maxIndex = i;
                }
            }

            if (maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(arrary, minIndex, left);
            swap(arrary, maxIndex, left);
            left++;
            right--;
        }
    }

    //堆排序
    public void heapSort(int[] array) {
        creatHeap((array));  //建堆
        int end = array.length - 1;  //确定最后一个结点的下标
        //当只剩下一个结点的时候就不用交换
        while (end > 0) {
            //交换
            swap(array, 0, end);
            //向下调整
            siftDown(array, 0, end);
            //调整完一个结点,减1
            end--;
        }

    }

    private void creatHeap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            siftDown(array, parent, array.length);
        }
    }
    //向下调整
    private void siftDown(int[] array, int parent, int len) {
        int child = (2 * parent) + 1;  //得到左孩子结点的下标
        while (child < len) {  //小于数组长度说明没调完
            if (child + 1 < len && array[child] < array[child + 1]) {
                //child+1小于usedsize说明没有越界
                //判断左孩子如果比右孩子小的话,child就要指向右孩子,因为下一步要用最大的孩子结点和父亲结点交换
                child = child + 1;
            }
            //程序执行到这一步就说明child一定是左右孩子最大值的下标
            if (array[child] > array[parent]) {  //child和parent找出最大值进行交换
                swap(array, child, parent);
                parent = child;  //继续向下调整
                child = 2 * parent + 1;
            } else {
                break;  //不用交换
            }
        }
    }

    public static void bubbleSort(int[] array) {
        //i代表趟数 10个数据比较的是9趟
        for (int i = 0; i < array.length - 1; i++) {
            boolean flg = false;
            //每一趟从下标0开始比较,每一趟比较都会少i+1次
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    flg = true;
                }
            }
            //如果没有交换就证明是有序的
            if (flg == false) {
                break;
            }
        }
    }

    public static void quickSort(int[] array) {  //为了统一排序算法接口
        quick(array, 0, array.length - 1);
    }

    private static void quick(int[] array, int start, int end) {
        if (start >= end) { //防止end到start后面越界,所以>=
            return;
        }
        //1.三数取中  index是中间大的数字的下标
        int index = middleNum(array, start, end);
        swap(array, index, start);

        int pivot = partition(array, start, end);  //先划分

        quick(array, start, pivot - 1); //递归左边

        quick(array, pivot + 1, end);  //递归右边

    }

    private static int middleNum(int[] array, int left, int right) {
        int mid = left + ((right - left) >> 1);

        if (array[left] < array[right]) {
            if (array[mid] < array[left]) {
                return left;    //例:x<3<9
            } else if (array[mid] > array[right]) {
                return right;
            } else {
                return mid;
            }
        } else {  //左边大于右边的
            if (array[mid] < array[left]) {
                return right;    //例:6>4>x
            } else if (array[mid] > array[right]) {
                return left;
            } else {
                return mid;
            }
        }
    }

    //快速排序的Hoare方法
    private static int partitionHoare(int[] array, int left, int right) {
        int tmp = array[left]; // 找一个基准
        int i = left;  //记录left的下标
        while (left < right) {  //直到相遇后退出循环
            while (left < right && array[right] >= tmp) {  //从最右边开始依次找个小于基准的数,
                right--;               //因为会出现右边的数全部大于基准数,right--会出现数组越界的情况,所以再加个left<right条件
            }

            while (left < right && array[left] <= tmp) {  //从最左边开始依次找个大于基准的数
                left++;
            }

            swap(array, left, right);  //经过上述程序步骤得到下标,交换
        }
        swap(array, i, left);  //I下标交换(left和right)下标相遇的位置,只交换值
        return left;  //返回相遇的位置
    }

    //前后指针法
    private static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        while (left < right) {
            //right往左边走
            while (left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];  //把right指向的值给left指向的位置
            //left往右边走
            while (left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left]; //把left指向的值给right的值
        }
        array[left] = tmp; //把基准放回去
        return left;
    }

    //归并排序

    public static void mergeSort(int[] array) {  //为了接口的统一性
        mergeFunc(array, 0, array.length - 1);
    }

    private static void mergeFunc(int[] array, int left, int right) {
        if (left >= right) {
            return;  //证明递归分解完毕
        }
        int mid = left + ((right - left) >> 1); //确定数组中间的元素  (>>1 是除2)

        //递归左边的子序列(分解)
        mergeFunc(array, left, mid);
        //递归右边的子序列(分解)
        mergeFunc(array, mid + 1, right);

        //左边右边分解完可以开始合并
        merge(array, left, mid, right);
    }

    //合并的方法
    private static void merge(int[] array, int left, int mid, int right) {
        //左子序列从left 开始
        int s1 = left;
        int e1 = mid;

        //右子序列从mid+1开始
        int s2 = mid + 1;
        int e2 = right;

        //创建一个新数组作为复制数组
        int[] tmpArr = new int[right - left + 1];
        int k = 0;

        //每次比较 都是S1和S2进行比较
        //2.如果一个表没有了数据,直接把另一个表剩下的数据全部拷贝进新数组

        //1.保证两个表都有数据
        while (s1 <= e1 && s2 <= e2) {
            if (array[s1] <= array[s2]) {
                //s1小的话就放进新数组
                tmpArr[k++] = array[s1++];  //s1放进数组后,新数组k要++,旧数组s1也要++
            } else {
                //反之s2放进新数组
                tmpArr[k++] = array[s2++];
            }
        }

        //2.看哪个数组还有数据,拷贝回去
        while (s1 <= e1) {  //证明s2已经走完了,直接把剩下的复制到新数组
            tmpArr[k++] = array[s1++];
        }
        while (s2 <= e2) {  //证明s1已经走完了,直接把剩下的复制到新数组
            tmpArr[k++] = array[s2++];
        }

        //把在新数组排好序的拷贝回原数组
        for (int i = 0; i < k; i++) {
            array[i + left] = tmpArr[i];  //拷贝回原数组要+left(下标不一定是从0开始的)
        }
    }

    //非递归实现归并排序
    public static void mergeSortNor(int[] array) {
        int gap = 1;
        //最外层控制组数
        while (gap < array.length) {
            //每一层进行排序
            for (int i = 0; i < array.length; i = i + 2 * gap) {
                int left = i;
                int mid = left + gap - 1;
                if(mid >= array.length) {  //预防越界
                    mid = array.length-1;
                }
                int right = mid + gap;
                if(right >= array.length) {  //预防越界
                    right = array.length-1;
                }

                merge(array,left,mid,right);
            }

            gap *= 2;
        }
    }

    //计数排序
    public static void countSort(int[] array) {
        //1.求最值
        int min = array[0];
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if(min>array[i]) {
                min = array[i];
            }
            if (max<array[i]) {
                max = array[i];
            }
        }
        //2.定义计数数组 进行初始化
        int[] count = new int[max-min+1];

        for (int i = 0; i < array.length; i++) {
            int index = array[i]-min; //防止出现90-99这种情况
            count[index]++;
        }

        //3.遍历计数数组
        int k = 0; //计数数组的下标
        for (int i = 0; i < count.length; i++) {
            while(count[i] != 0) {
                array[k] = i+min;  //写回到原数组
                k++;
                count[i]--;
            }
        }
    }
}